//区间左端点二分模板链接：https://www.luogu.com.cn/problem/P2249#submit
//左右端点二分模板链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
      vector<int> ret(2);
      int n = nums.size();
      if(n == 0) return {-1,-1};
      int l = 0 , r = n-1;
      while(l < r)
      {
        //查找区间左端点
        //< , >=
        int mid = l + ((r-l) >>1);
        if(nums[mid] >= target) r = mid;
        else l = mid+1;
      }
      if(nums[l] != target) ret[0] = ret[1] = -1;
      else 
      {
        ret[0] = l;
        int l = 0 , r = n-1;
        while(l < r)
        {
            //查找区间右端点
            //<= , >
            int mid = l + ((r - l+1) >> 1);
            if(nums[mid] <= target) l = mid;
            else r = mid -1;
        }
        ret[1] = l;
      }
      return ret;
    }
};
// #include <iostream>
// using namespace std;
// int n;
// int m;
// const int N = 1e6+10;
// int a[N];
// int main()
// {
//     scanf("%d %d",&n,&m);
//     for(int i = 0 ; i < n ; ++i) scanf("%d",&a[i]);
//     while(m--)
//     {
//         //查找区间左端点
//         int t;
//         scanf("%d",&t);
//         int l = 0 , r = n-1;
//         while(l < r)
//         {
//             //<t   >=t
//             int mid = (l + r)/2;
//             if(a[mid] >= t) r = mid;
//             else l = mid+1;
//         }
//         if(a[l] != t) printf("-1 ");
//         else printf("%d ",l+1);
//     }
//     return 0;
// }


// #include <iostream>
// using namespace std;
// const int N = 1e6 + 10;
// int a[N];
// int main()
// {
//     int n , m;
//     cin >> n >> m;
//     for(int i = 0 ; i < n ; ++i) scanf("%d",&a[i]);
//     while(m--)
//     {
//         //查找区间右端点
//         // <= , >
//         int t;
//         scanf("%d",&t);
//         int l = 0 , r = n-1;
//         while(l < r)
//         {
//             int mid = l + (r-l+1>>1);
//             if(a[mid] <= t) l = mid;
//             else r = mid-1;
//         }
//         if(a[l] != t) printf("-1 ");
//         else printf("%d ",l);
//     }
//     return 0;
// }
